#include "cache.h"

typedef struct CACHERECORD
{
    RR* record;
    int timeArrive;
    struct CACHERECORD* previous, * next;
} crecord;
crecord chead, tail;

struct NODE;
typedef struct NODE node;

struct NODE
{
    int height;
    crecord* data;
    node* leftSon, * rightSon, * father;
};
node* tree;

int tot = -1;

//void delete(unsigned char* domain, node** t);

#define height(a) (a == NULL ? -1 : a->height)
node* newNode(crecord* data, node* father)
{
    node* p = malloc(sizeof(node));
    memset(p, 0, sizeof(node));
    p->data = data;
    p->father = father;
    return p;
}

node* findPos(unsigned char* domain, node* pos)
{
    int cmp;
    if (pos == NULL)
        return pos;
    cmp = strcmp(pos->data->record->domain, domain);
    if (cmp == 0)
        return pos;
    if (cmp < 0)
        return findPos(domain, pos->rightSon);
    else
        return findPos(domain, pos->leftSon);
}

#define max(a,b) ((a)>(b))?(a):(b)

void update(node* pos)
{
    if (pos == NULL)
        return;
    pos->height = max(height(pos->rightSon), height(pos->leftSon)) + 1;
}

void rotateR(node* pos)
{
    node* father = pos->father;
    if (father != NULL)
    {
        if (father->rightSon == pos)
        {
            father->rightSon = pos->rightSon;
        }
        else
        {
            father->leftSon = pos->rightSon;
        }
    }
    pos->father = pos->rightSon;
    if (pos->rightSon->leftSon != NULL)
    {
        pos->rightSon = pos->rightSon->leftSon;
        pos->rightSon->father = pos;
    }
    else
    {
        pos->rightSon = NULL;
    }
    pos->father->leftSon = pos;
    pos->father->father = father;
    update(pos);
    update(pos->father);
    update(father);
}
void rotateL(node* pos)
{
    node* father = pos->father;
    if (father != NULL)
    {
        if (father->rightSon == pos)
        {
            father->rightSon = pos->leftSon;
        }
        else
        {
            father->leftSon = pos->leftSon;
        }
    }
    pos->father = pos->leftSon;
    if (pos->leftSon->rightSon != NULL)
    {
        pos->leftSon = pos->leftSon->rightSon;
        pos->leftSon->father = pos;
    }
    else
    {
        pos->leftSon = NULL;
    }
    pos->father->rightSon = pos;
    pos->father->father = father;
    update(pos);
    update(pos->father);
    update(father);
}
int getBalanceFactor(node* pos)
{
    if (pos == NULL) return 0;
    return height(pos->leftSon) - height(pos->rightSon);
}
void fix(node* pos)
{
    update(pos);
    int balanceFactor = getBalanceFactor(pos);
    if (balanceFactor == 2)
    {
        if (getBalanceFactor(pos->leftSon) == 1)
        {
            rotateL(pos);
        }
        else
        {
            rotateR(pos->leftSon);
            rotateL(pos);
        }
    }
    else if (balanceFactor == -2)
    {
        if (getBalanceFactor(pos->rightSon) == -1)
        {
            rotateR(pos);
        }
        else
        {
            rotateL(pos->rightSon);
            rotateR(pos);
        }
    }
}
node* insert(crecord* data, node* pos)
{
    node* final;
    if (strcmp(pos->data->record->domain, data->record->domain) > 0)
    {
        if (pos->leftSon == NULL)
        {
            final = newNode(data, pos);
            pos->leftSon = final;
        }
        else
            final = insert(data, pos->leftSon);
    }
    else
    {
        if (pos->rightSon == NULL)
        {
            final = newNode(data, pos);
            pos->rightSon = final;
        }
        else
            final = insert(data, pos->rightSon);
    }
    fix(pos);
    return final;
}
crecord* deleteMin(node** t)
{
    node* preroot;
    crecord* minValue;

    if ((*t)->leftSon == NULL)
    {
        /* root is min value */
        preroot = *t;
        minValue = preroot->data;
        *t = preroot->rightSon;
        free(preroot);
    }
    else
    {
        /* min value is in left subtree */
        minValue = deleteMin(&(*t)->leftSon);
    }
    fix(*t);
    return minValue;
}

void delete (unsigned char* domain, node** t)
{
    node* p;
    if (t == NULL || *t == NULL)
        return;
    int cmp = strcmp((*t)->data->record->domain, domain);
    if (cmp == 0)
    {
        if ((*t)->rightSon != NULL)
        {
            (*t)->data = deleteMin(&(*t)->rightSon);
        }
        else
        {
            p = (*t);
            *t = (*t)->leftSon;
            free(p);
        }
    }
    else
    {
        delete (domain, cmp > 0 ? (&((*t)->leftSon)) : (&((*t)->rightSon)));
    }
    fix(*t);
}

void cache_init()
{
    chead.next = &tail;
    tail.previous = &chead;
}

void cache_delete(crecord* ptr)
{
    if (ptr == NULL)
        return;
    ptr->next->previous = ptr->previous;
    ptr->previous->next = ptr->next;
    --tot;
    delete (ptr->record->domain, &tree);
    free(ptr->record->domain);
    free(ptr->record->rdata);
    free(ptr->record);
    free(ptr);
}

void cache_insert(RR* record, int timeArrive)
{
    crecord* ptr = malloc(sizeof(crecord));
    ptr->record = record;
    ptr->timeArrive = timeArrive;
    if (tree != NULL)
        insert(ptr, tree);
    else
    {
        tree = newNode(ptr, NULL);
    }
    if (tot == LRU_SIZE)
    {
        cache_delete(chead.next);
    }
    tail.previous->next = ptr;
    ptr->previous = tail.previous;
    ptr->next = &tail;
    tail.previous = ptr;
    ++tot;
}

RR* cache_find(unsigned char* domain, int timeNow)
{
    node* p = findPos(domain, tree);
    if (p == NULL)
        return NULL;
    else if ((ntohl(p->data->record->ttl) + p->data->timeArrive) < timeNow)
    {
        cache_delete(p->data);
        return NULL;
    }
    else
    {
        RR* rt = p->data->record;
        rt->ttl = htonl(ntohl(rt->ttl) - (timeNow - p->data->timeArrive));
        p->data->timeArrive = timeNow;
        p->data->previous->next = p->data->next;
        p->data->next->previous = p->data->previous;
        p->data->previous = tail.previous;
        p->data->next = &tail;
        p->data->previous->next = p->data;
        tail.previous = p->data;
        return rt;
    }
}
